[YZOJ1370]无聊的锤锤

发表于 | 分类于 ， | | 阅读次数:

题目

题目描述

罗宏明（白客），1988年7月9日出生于中国山东省泰安市，中国内地新生代男演员，毕业于中国传媒大学南广学院。原先是配音员，《搞笑漫画日和》配音团队cucn201的主要成员之一。2013年因出演导演叫兽易小星的搞笑网剧《万万没想到》中的男一号“王大锤”，从而备受关注。
这么火的搞笑剧中，大家是否注意到这样一个剧情(没看过也没关系的)：王大锤要回家过年，上司不让，无奈之下，王大锤就发挥了自己的聪明才智，决定和上司玩个游戏，想着锤锤是个数学白痴，上司欣然答应，胜了就让他回家。游戏是这样的,开始时，白板上有两个不等的整数，他们轮流行动，每次行动必须在白板上写出任意两个已在白板上出现的整数的差且非负，而且这个数字必须是新的，谁再也写不出来就输了。
为了彰显上司魅力，上司让锤锤先开始。上司足够聪明，当然王大锤也不笨，不然会这么火吗？如果你事先知道白板上的数字，聪明的你能推理出王大锤能否回家呢？

输入

测试数据有多组，每组有两个整数，即白板上最初的数字，数据保证在int范围内。

输出

每组测试数据输出一行，锤锤能回家就输出“1”，不能输出“0”。

样例输入

1
2
5 3
4 8

样例输出

1
2
1
0

题解

一开始还打算用暴力，写到一般就打消了这个念头。其实显而易见的是，对于正整数n,m来说,这两个数相减可以得出的所有数x,则
公式

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<cstdio>
using namespace std;

int gcd(int a,int b){
	return b==0?a:gcd(b,a%b);
}

int main(){
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF){
		int num=gcd(n,m);
		int c1=n/num;//看它最多能写几个数
		int c2=m/num;
		if(c1>c2)printf("%d\n",c1%2);
		else printf("%d\n",c2%2);
	}
	return 0;
}